/* Copyright (C) 
 * 
 * Disclaim
 * This program is the property of AI Speech Ltd. It shall be communicated to
 * authorized personnel only. It is not to be disclosed outside the group without
 * prior written consent. If you are not sure if you’re authorized to read this
 * program, please contact info@aispeech.com before reading.
 * 
 */

/**
 * @file wtk_utils_str_dis.c
 * 
 * @author wxm71(weixing.mei@aispeech.com)
 * 
 * @version 0.0.2
 * 
 * @date 2015-04-16
 */

#include <stdlib.h>
#include <math.h>

#include "wtk_utils_ustr.h"
#include "wtk_utils.h"

int wtk_utils_str_dis_lcs(char *dataL, int lenL, char *dataR, int lenR) {
    if(lenL==0) {
        return lenR;
    }

    if(0==lenR) {
        return lenL;
    }

    wtk_utils_ustr_t *ustrL = wtk_utils_ustr_new(dataL, lenL, 1);
    wtk_utils_ustr_t *ustrR = wtk_utils_ustr_new(dataR, lenR, 1);

    int numL = wtk_utils_ustr_get_num(ustrL);
    int numR = wtk_utils_ustr_get_num(ustrR); 

    wtk_string_t strL;
    wtk_string_t strR;

    int i;
    int j;
    int val;
    int tmp;
    int **buf = calloc(lenL+1, sizeof(int*));

    // buf[i][j]: lcs of substring dataL[0:i] and dataR[0:j]
    for(i=0; i<=numL; ++i) {
        buf[i] = calloc(lenR+1, sizeof(int));
    }

    for(i=1; i<=numL; ++i) {
        strL = wtk_utils_ustr_at(ustrL, i-1);

        for(j=1; j<=numR; ++j) {
            strR = wtk_utils_ustr_at(ustrR, j-1);

            if(wtk_utils_s_equ(strL.data, strL.len, strR.data, strR.len)) {
                val = 1;
            } else {
                val = 0;
            }

            val += buf[i-1][j-1];

            tmp = buf[i][j-1];
            if(tmp>val) {
                val = tmp;
            }

            tmp = buf[i-1][j];
            if(tmp>val) {
                val = tmp;
            }

            buf[i][j] = val;
        }
    }

    val = buf[numL][numR];

    for(i=0; i<=numL; ++i) {
        free(buf[i]);
    }
    free(buf);
    wtk_utils_ustr_delete(ustrL);
    wtk_utils_ustr_delete(ustrR);

    return val;
}


int wtk_utils_str_dis_lccs(char *dataL, int lenL, char *dataR, int lenR) {
    return 0;
}


int wtk_utils_str_dis_edit(char *dataL, int lenL, char *dataR, int lenR) {
    if(lenL==0) {
        return lenR;
    }

    if(0==lenR) {
        return lenL;
    }

    wtk_utils_ustr_t *ustrL = wtk_utils_ustr_new(dataL, lenL, 1);
    wtk_utils_ustr_t *ustrR = wtk_utils_ustr_new(dataR, lenR, 1);

    int numL = wtk_utils_ustr_get_num(ustrL);
    int numR = wtk_utils_ustr_get_num(ustrR); 

    wtk_string_t strL;
    wtk_string_t strR;

    int i;
    int j;
    int dis;
    int tmp;
    int **buf = calloc(lenL+1, sizeof(int*));

    // buf[i][j]: distance of substring dataL[0:i] and dataR[0:j]
    for(i=0; i<=numL; ++i) {
        buf[i] = calloc(lenR+1, sizeof(int));
        buf[i][0] = i;
    }

    for(i=0; i<=numR; ++i) {
        buf[0][i] = i;
    }

    for(i=1; i<=numL; ++i) {
        strL = wtk_utils_ustr_at(ustrL, i-1);

        for(j=1; j<=numR; ++j) {
            strR = wtk_utils_ustr_at(ustrR, j-1);

            if(wtk_utils_s_equ(strL.data, strL.len, strR.data, strR.len)) {
                dis = 0;
            } else {
                dis = 1;
            }

            dis += buf[i-1][j-1];

            tmp = buf[i][j-1]+1;
            if(tmp<dis) {
                dis = tmp;
            }

            tmp = buf[i-1][j]+1;
            if(tmp<dis) {
                dis = tmp;
            }

            buf[i][j] = dis;
        }
    }

    dis = buf[numL][numR];

    for(i=0; i<=numL; ++i) {
        free(buf[i]);
    }
    free(buf);
    wtk_utils_ustr_delete(ustrL);
    wtk_utils_ustr_delete(ustrR);

    return dis;
}


float wtk_utils_str_sim_edit(char *dataL, int lenL, char *dataR, int lenR) {
    int dis = wtk_utils_str_dis_edit(dataL, lenL, dataR, lenR); 

    wtk_utils_ustr_t *ustrL = wtk_utils_ustr_new(dataL, lenL, 1);
    wtk_utils_ustr_t *ustrR = wtk_utils_ustr_new(dataR, lenR, 1);

    int numL = wtk_utils_ustr_get_num(ustrL);
    int numR = wtk_utils_ustr_get_num(ustrR); 
    
    if(numR>numL) {
        numL = numR;
    }

    float wgt = 1-(float)dis/numL;

    wtk_utils_ustr_delete(ustrL);
    wtk_utils_ustr_delete(ustrR);

    return wgt*wgt;
}


float wtk_utils_str_sim_lcs(char *dataL, int lenL, char *dataR, int lenR) {
    int dis = wtk_utils_str_dis_lcs(dataL, lenL, dataR, lenR); 

    wtk_utils_ustr_t *ustrR = wtk_utils_ustr_new(dataR, lenR, 1);
    int numR = wtk_utils_ustr_get_num(ustrR); 
    
    float wgt = (float)dis/numR;

    wtk_utils_ustr_delete(ustrR);

    return wgt*wgt;
}
